package thuai.ccf2013.util;

import java.util.ArrayList;
import java.util.List;

public class MyStrUtil {
	
	public static String getRidOfSymbol(String input) {
		return MyStrUtil.getRidOfAllChar(input, "《》,\"“”<>.？·");
	}
	
	public static boolean hasCommonChar(String str1, String str2) {
		for (int i = 0; i < str1.length(); i++) {
			if (str2.contains(str1.charAt(i) + "")) {
				return true;
			}
		}
		return false;
	}
	
	/*
	 * This function is cited from web
	 * http://blog.csdn.net/iloveyou1098/article/details/6606486#
	 */
	public static String comSubstring(String str1, String str2) {
		char[] a = str1.toCharArray();
		char[] b = str2.toCharArray();
		int a_length = a.length;
		int b_length = b.length;
		int[][] lcs = new int[a_length + 1][b_length + 1];
		// 初始化数组
		for (int i = 0; i <= b_length; i++) {
			for (int j = 0; j <= a_length; j++) {
				lcs[j][i] = 0;
			}
		}
		for (int i = 1; i <= a_length; i++) {
			for (int j = 1; j <= b_length; j++) {
				if (a[i - 1] == b[j - 1]) {
					lcs[i][j] = lcs[i - 1][j - 1] + 1;
				}
				if (a[i - 1] != b[j - 1]) {
					lcs[i][j] = lcs[i][j - 1] > lcs[i - 1][j] ? lcs[i][j - 1]
							: lcs[i - 1][j];
				}
			}
		}
	
		// 由数组构造最小公共字符串
		int max_length = lcs[a_length][b_length];
		char[] comStr = new char[max_length];
		int i =a_length, j =b_length;
		while(max_length>0){
			if(lcs[i][j]!=lcs[i-1][j-1]){
				if(lcs[i-1][j]==lcs[i][j-1]){//两字符相等，为公共字符
					comStr[max_length-1]=a[i-1];
					max_length--;
					i--;j--;
				}else{//取两者中较长者作为A和B的最长公共子序列
					if(lcs[i-1][j]>lcs[i][j-1]){
						i--;
					}else{
						j--;
					}
				}
			}else{
				i--;j--;
			}
		}
//		System.out.print("最长公共字符串是：");
//		System.out.print(comStr);
		return new String(comStr);
	}
	
	public static String[] SUFFIX = new String[] {
		"国", "省", "市", "县", "区", "乡", "镇", "村", "自治区", "沟",
		"队", "网", "公司", "集团",
	};
	
	public static String getRidOfSuffix(String input) {
		for (int i = 0; i < SUFFIX.length; i++) {
			if (input.contains(SUFFIX[i])) {
				input = input.substring(0, input.indexOf(SUFFIX[i]));
			}
		}
		return input;
	}
	
	/**
	 * Return true if a is prefix of b or b is prefix of a.
	 * @param a
	 * @param b
	 * @return
	 */
	public static boolean isBegin(String a, String b) {
		return a.startsWith(b) || b.startsWith(a);
	}
	
	/**
	 * Return true when a is substring of b or b is substring of a.
	 * @param a
	 * @param b
	 * @return
	 */
	public static boolean isCover(String a, String b) {
		return a.contains(b) || b.contains(a);
	}
	
	/**
	 * Any character in splitter could divide the src String into different parts.
	 * @param src
	 * @param splitter
	 * @return
	 */
	public static List<String> multiCut(String src, String splitter) {
		
		List<String> seg = new ArrayList<String>();
		int begin = 0;
		for (int i = 0; i < src.length(); i++) {
			if (splitter.contains("" + src.charAt(i))) {
				if (i > begin) {
					seg.add(src.substring(begin, i));
				}
				begin = i + 1;
			}
		}
		return seg;
	}
	
	public static String getRidOfAllChar(String src, String badchars) {
		StringBuilder sb = new StringBuilder();
		int begin = 0, i = 0;
		for (i = 0; i < src.length(); i++) {
			if (badchars.contains("" + src.charAt(i))) {
				if (i > begin) {
					sb.append(src.substring(begin, i));
				}
				begin = i + 1;
			}
		}
		if (i > begin) {
			sb.append(src.substring(begin, i));
		}
		return sb.toString();
	}
	
	/**
	 * Cited from Wikipedia, Levenshtein Distance
	 * 
	 * @param s
	 * @param t
	 * @return
	 */
	public static int LevenshteinDistance(String s, String t) {
		// degenerate cases
		if (s == t)
			return 0;
		if (s.length() == 0)
			return t.length();
		if (t.length() == 0)
			return s.length();

		// create two work vectors of integer distances
		int[] v0 = new int[t.length() + 1];
		int[] v1 = new int[t.length() + 1];

		// initialize v0 (the previous row of distances)
		// this row is A[0][i]: edit distance for an empty s
		// the distance is just the number of characters to delete from t
		for (int i = 0; i < v0.length; i++)
			v0[i] = i;

		for (int i = 0; i < s.length(); i++) {
			// calculate v1 (current row distances) from the previous row v0

			// first element of v1 is A[i+1][0]
			// edit distance is delete (i+1) chars from s to match empty t
			v1[0] = i + 1;

			// use formula to fill in the rest of the row
			for (int j = 0; j < t.length(); j++) {
				int cost = (s.charAt(i) == t.charAt(j)) ? 0 : 2;
				v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
			}

			// copy v1 (current row) to v0 (previous row) for next interation
			for (int j = 0; j < v0.length; j++)
				v0[j] = v1[j];
		}
		return v1[t.length()];
	}
	
	public static int Minimum(int a, int b, int c) {
		if (a < b) {
			return a < c ? a : c;
		} else {
			return b < c ? b : c;
		}
	}

}
